컨테이너(Container)
표준 라이브러리 컨테이너는 중요한 자료 구조를 광범위하게 포함하고 있으며,
사용하기 쉽고 매우 효율적이다.
벡터
#include <vector>
가장 간단한 STL 컨테이너로 C 배열과 유사하게 데이터를 연속적으로 저장하는데 효율적이다.
특정 크기를 갖는 C 배열은 스택에 저장되지만, vector는 항상 힙에 상주한다.
벡터는 첨자 연산자(operaotr[])를 제공하며, 배열 스타일의 알고리즘을 사용할 수 있다.
#include <vector>
std::vector<int> v={3, 4, 7, 9};
for(int i=0; i<v.size(); ++i) v[i]*=2;
// or
for(auto& x: v) x*=2;
항목 추가
my_random()을 난수 생성기인 경우
std::vecot<int> v;
for(int i=0; i<100; ++i) v.push_back(my_random());
- 이미 예약된 공간을 채우는 경우 속도가 상당히 빠르다.
- 더 많은 메모리를 할당하고 모든 데이터를 복사해야 하는 경우 속도가 느려진다.
사용 가능한 공간은 capacity() 멤버함수를 통해 알 수 있다.
vector의 데이터의 크기가 커질 경우, 추가 공간의 양은 벡터 크기에 비례한다.
push_back은 점근적으로 상수 시간을 갖는다.
일반적으로 벡터의 크기가 2배가 될 때 메모리를 두 번 할당하도록 구현되어 있다.
(추가 공간이 꽉차면, 새로운 메모리를 할당해야 하며 새로운 메모리에 기존에 존재하는 데이터를 복사해야 한다.)
resize(n) 메서드는 벡터의 크기를 n으로 줄이거나 키운다.
(새로운 항목은 디폴트 생성자(내장 타입의 경우 0)로 생성)
resize로 벡터의 크기를 조정해도 메모리를 해제하지는 않음
C++11에 shrink_to_fit 메서드가 추가되었다.
shrink_to_fit 메서드는 벡터의 용량(capacity)을 실제 벡터의 크기(size)로 줄인다.
#include <iostream>
#include <vector>
#include <algorithm>
int main(void){
using namespace std;
vector<int> v={3, 4, 7, 9};
auto it=find(v.begin(), v.end(), 4);
cout<<"After "<<*it<<" comes "<<*(it+1)<<'\n';
auto it2=v.insert(it+1, 5);
v.erase(v.begin());
cout<<"Size= "<<v.size()<<", capacity= "<<v.capacity()<<'\n';
v.shrink_to_fit();
v.push_back(7);
for(auto i: v) cout<<i<<" ,";
cout<<'\n';
}
After 4 comes 7
Size= 4, capacity= 8
4 ,5 ,7 ,9 ,7 ,
vector에서 값을 중간에 insert하면, 뒤에 값을 다 뒤로 미뤄줘야 하기 때문에 비용이 많이 듬
C++11에서 emplace, emplace_back 메서드가 추가되었다.
vector<matrix> v;
v.push_back(matrix(3, 7)); // 3*7 행렬 추가, 바깥에서 생성
v.emplace_back(matrix(7, 9)); // 7*9 행렬 추가, 안에서 생성
push_back을 사용하면, 먼저 개체를 생성한 이후 벡터의 새로운 항목으로 복사하거나 이동한다.
emplace_back은 새로운 개체를 벡터의 새로운 항목에 직접 생성한다.
emplace_back 사용시, 복사 또는 이동 작업과 일부 메모리 할당/해제를 절약할 수 있다.
컴파일 시에 벡터의 크기를 알고 있으며 나중에 크기가 변하지 않는다면 벡터 대신
C++11 컨테이너 array를 사용할 수 있다.
array는 스택에 상주하기 때문에 보다 효율적이다.
(move 및 swap과 같은 얕은 복사 작업은 비효율적)
vector member
양쪽으로 사용할 수 있는 큐(deque)
#include <deque>
deque(Double-Ended QUEue)는 여러 각도에서 접근 가능하다.
- FIFO(First-In First-Out) 큐
- LIFO(Last-In First-Out) 큐
- 앞쪽에서 빠른 삽입을 하는 vector의 일반화
deque 컨테이너는 내부적으로 여러 개의 하위 컨테이너로 구성된다.
새로운 항목을 추가하면 마지막 하위 컨테이너의 끝에 삽입되고, 해당 항목이 가득차면
새로운 하위 컨테이너를 할당한다.
위와 같은 구조는 대부분의 메모리를 순차적으로 저장하게 되며(같은 하위 컨테이너는 순차적)
접근 속도가 vector와 거의 비슷하다
deque 항목은 절대로 재배치되지 않는다.
(복사 또는 이동 비용을 절약할 분만 아니라 복사 및 이동이 불가능한 타입도 저장할 수 있다.)
C++11 emplace 메서드를 사용하면 복사 불가능한, 이동 불가능한 클래스의 컨테이너를 만들 수 있다.
ex) atomic 멤버 때문에 복사 생성자나 이동 생성자를 포함하지 않는 solver 클래스
struct parameters{};
struct solver{
solver(const mat& ref, const parameters& para): ref(ref), para(para) {}
solver(const solver&)=delete; // 이동 생성자 삭제
solver(solver&&)=delete; // 복사 생성자 삭제
const mat& ref;
const parameter& para;
};
solver의 여러 개체를 deque에 정장하는 경우
void solve_x(const solver& s){ ... }
int main(void){
parameters p1, p2, p3;
mat A, B, C;
deque<solver> solvers;
solvers.push_back(solver(A, p1)); // can't compile
solvers.emplace_back(B, p1);
solvers.emplace_back(C, p2);
solvers.emplace_back(A, p1);
for(auto& s: solvers) solver_x(s);
return 0;
}
복사 및 이동 생성자가 정의되지 않은 클래스를 템플릿으로 할 경우,
deque의 insert 및 delete 메서드를 사용할 수 없으며,
for(auto s: solvers)로 사용할 경우, 복사가 필요하기 때문에
for(auto& s: solvers)와 같이 레퍼런스를 사용해야 한다.
리스트(List)
#include <list>
std::list 컨테이너는 이중 링크드 리스트로 앞 또는 뒤로 탐색할 수 있다.(Bidirectional Iterator)
Vector나 Deque와 달리, n번째 항목에 직접 접근할 수 없다.
List는 대신 중간에 삭제와 삽입하는 비용이 더 저렴하다.
리스트에 있는 항목은 다른 항목을 삽입하거나 삭제하더라도 절대로 움직이지 않는다.
따라서 삭제한 항목의 레퍼런스와 반복자만 무효화되고 나머지는 유효하다.
int main(void){
list<int> l={3, 4, 7, 9};
auto it=find(begin(l), end(l), 4), it2=find(begin(l), end(l), 7);
l.erase(it);
cout<<"it2 still points to "<<*it2<<'\n';
return 0;
}
개별 항목의 동적 메모리 처리는 메모리상에서 각 항목을 분산시키기 때문에 캐시 동작을 발생시킨다.
(vector와 deque보다 성능이 떨어진다)
list<int>의 항목은 일반적으로 64비트 플랫폼 기준 20바이트를 사용한다.
64비트 포인터 2개(forward, backward): 2 x 8 byte
int type: 4 bye
역방향 반복자가 필요하지 않은 경우, forward_list를 사용하면, 포인터 하나의 공간을 절약할 수 있다.
#include <forward_list>
Set & Multiset
#include <set>
set 컨테이너는 집합에 속하는 값 정보를 저장하는데 사용된다.
(내부적으로 tree로 정렬되어 있음, O(n)의 시간 복잡도로 접근)
트리에 정렬하여 저장(이진탐색트리자료구조 사용)
set에 값의 유무는 find(), count() 멤버함수로 할 수 있다.
find() 메서드는 값을 참조하는 반복자를 반환하고 찾지 못한 경우, end 반복자를 반환한다.
반복자가 필요하지 않은 경우, count()가 더 유용하다
set<int> s={1, 3, 4, 7, 9};
s.insert(5);
for(int i=0; i<6; ++i){
cout<<i<<" appears "<<s.count(i)<<"time(s).\n";
}
set에서 요소의 개수는 항상 0, 1개 이다.
multiset은 set에서 값을 삽입하는 빈도를 추가적으로 계산한다.
multiset<int> s={1, 3, 4, 7, 9, 1, 1, 4};
s.insert(4);
for(int i=0; i<6; ++i){
cout<<i<<" appears "<<s.count(i)<<"times(s).\n";
}
Map & Multimap
#include <map>
map은 연관 컨테이너이다.(값이 키(Key)와 연관된다.)
키는 순서가 있는 모든 타입을 가질 수 있다.
순서는 less 펑터를 통해 operator< 또는 Strict Weak Ordering을 설정하는 펑터로 제공
map은 간결한 접근을 위한 첨자 연산자( opeartor[] )를 지원
map<string, double> constants={{"e", 2.7}, {"pi", 3.14}, {"h", 6.6e-34}};
cout<<"The Planck constant is "<<constants["h"]<<'\n';
constants["c"]=299792458;
cout<<"The Coulomb constants is "<< constants["k"]<<'\n'; // 없는 항목 접근
cout<<"The circle's circumference pi is "<<constants.find("pi")->second<<'\n';
// 존재하지 않는 키값을 찾는 경우, 생성자가 값0을 가지는 항목을 생성한다.
auto it_phi=constants.find("phi"); // 존재하지 않는 항목
if(it_phi!=constants.end()) cout<<"Golden ratio is "<<it_phi->second<<'\n';
// 존재하지 않는 항목에 대한 순환자는 end()를 포인팅
cout<<"The Euler constant is "<<constants.at("e")<<"\n\n";
for(auto& c: constants) cout<<"The value of "<<c.first<<" is "<<c.second<<'\n';
// sort로 자동으로 key값을 기준으로 정렬
맵은 키-값 쌍으로 이루어진 리스트로 초기화한다.
pair<const string, double>
첨자 연산자를 이용해서 값을 찾거나, 새로운 쌍을 대입할 수 있다.
(첨자 연산자는 해당 키의 값을 가르키는 레퍼런스를 반환하며,
키를 찾을 수 없는 경우 새로운 항목을 디폴트 생성된 값으로 삽입한다.
그리고 디폴트 생성자로 생성한 값(value)의 레퍼런스를 반환)
존재하지 않는 키를 첨자 연산자로 검색하게 되면, 뜻하지 않게 해당 키에 대한
default value=0인 항목을 생성한다.
map에서 키-값 검색에서 operator[], find(), at() 메서드를 사용할 수 있다.
(at()은 C++11부터)
find는 operator[]처럼 존재하지 않는 키값에 대하여 새로 값을 생성하지 않고,
end() 반복자를 반환한다.
(find()는 키-값 쌍을 참조하는 const_iter ator를 반환한다.)
at() 메서드는 값을 가르키는 레퍼런스를 반환한다.
키를 발견하지 못하는 경우, out_of_range 예외를 발생시킨다.
(항목을 찾는데 사용한다면, at() 메서드를 사용하는 것이 좋음)
| map | return type | key 존재하지 않을 경우 |
| operator[] | 값 레퍼런스 | 값 0으로 하는 항목 생성 |
| find() | const_iter ator(반복자) | end 반복자 반환 |
| at() | 값 레퍼런스 | out_of_range exception |
Multiset은 키가 여러 값과 연관되는 경우 사용한다.
동일한 키를 같는 항목은 서로 간에 저장되어 있기 때문에 반복문을 수행할 수 있다.
(반복자 lower_bound, upper_bound 메서드사용)
multimap<int, double> mm={{3, 1.3}, {2, 4.1}, {3, 1.8}, {4, 9.2}, {3, 1.5}};
for(auto it=mm.lower_bound(3), end=mm.upper_bound(3)); it!=end; ++it){
cout<<"The Key 3 value is "<<it->second<<'\n';
}
set, multiset, map, multimap은 모두 일종의 트리로 인식되며
단일 항목에 접근하는데 걸리는 시간 복잡도는 O(log n) 다.
Hash Table(unordered_map)
Hash Table은 매우 효율적으로 검색할 수 있는 알고리즘이다.
(단일 항목 접근에 O(1)의 시간 복잡도를 가진다.)
unordered_map<string, double> constants={{"e", 2.7}, {"pi", 3.14}, {"h", 6.6e-34}};
cout<<"The Planck constants is "<<constants["h"]<<'\n';
constants["c"]=299792458;
cout<<"The Euler constants is "<<constants.at("e")<<""\n\n";
모든 컨테이너(STL)은 사용자 정의 가능한 할당자를 제공하여 자체적으로 메모리 관리를 구현하거나
플랫폼마다 서로 다른 메모리를 사용할 수 있도록 지원한다.